package arithmetic;

import java.util.Arrays;
import java.util.Random;

/**
 * 选择排序
 * url:https://www.hello-algo.com/chapter_sorting/selection_sort/
 */
public class SelectionSort {


    /**
     * 排序过程：
     *  1.初始状态,所有元素未排序,即[0~n-1]未排序区间
     *  2.选取区间[0~i-1]中最小的元素,记为minIndex，将其与索引0处的元素交换。完成后，数组前1个元素已排序。
     *  3.选取区间 [1~i-1]中的最小元素，将其与索引1处的元素交换。完成后，数组前 2 个元素已排序。
     *  4.以此类推。经过 n-1 论选择后，数组前n-1个元素已排序。
     *  5.仅剩的一个元素必定是最大元素，无需排序，因此排序完成。
     * @param array
     */
    void selectionSort(int[] array){
        //总长度
        int n = array.length;
        for(int i = 0;i<n-1;i++){
            int minIndex = i;
            for(int j = i+1;j<n;j++){
                if(array[minIndex] > array[j]){
                    minIndex = j;
                }
            }
            int temp = array[minIndex];
            array[minIndex] = array[i];
            array[i] = temp;
        }
    }

    public static void main(String[] args) {
        //生成随机数组
        Random random = new Random();
        int n = 10;
        int[] array = new int[n];
        for(int i = 0;i<n;i++){
            array[i] = random.nextInt(500);
        }
        System.out.println("原始数组：" + Arrays.toString(array));
        new SelectionSort().selectionSort(array);
        for(int i:array){
            System.out.println(i);
        }
    }
}
